package lcs.table;

import java.util.LinkedList;
import java.util.List;


/**
 * TableSearcher is a utility class that uses a populated table 
 * to find all the LCS values of a FinderTable.
 */
public class CompleteTableSearchHandler {
	//searchResult holds the list of LCSs
	private List<String> searchResult = new LinkedList<String>();

	/**
	 * Launches the recursive searchTable, returns solutions
	 * 
	 * @param table The table to search
	 * @return The LCS values of the table.
	 */
	public List<String> searchTable(FinderTable table)
	{
		searchTable(table,table.getStringX().length()-1,table.getStringY().length()-1,"");
		return searchResult;
	}

	/**
	 * Recursively searches the FinderTable for common substructures
	 * 
	 * @param table The table to search.
	 * @param searchX The starting X value of the search.
	 * @param searchY The starting Y value of the search.
	 * @param currResult The lcs as it has been constructed thus far.
	 */
	private void searchTable(FinderTable table, int searchX, int searchY, String currResult) //TODO: clean up code
	{
		if (searchX==0 && searchY==0) { //if the search is over
			if ( //if the first letter of both strings is the same, append
					table.getStringX().charAt(0) ==
					table.getStringY().charAt(0))
				currResult=table.getStringX().charAt(0)+currResult; //append found character to beginning of result string
			checkResult(currResult);
		} else if ( //if we are searching in the top row, and left is less than current
				searchX==0 &&
				table.getElementAt(searchX, searchY-1).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			currResult=table.getStringX().charAt(searchX)+currResult; //add found match
			searchTable(table,0,searchY-1,currResult); //continue search from 0,y-1
		} else if ( //if we are searching in the leftmost column, and above is less than current
				searchY==0 &&
				table.getElementAt(searchX-1, searchY).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			currResult=table.getStringX().charAt(searchX)+currResult; //add found match
			searchTable(table,searchX-1,0,currResult); //continue search from x-1,0
		} else if ( //if we are searching in the top row, and left is equal to current
				searchX==0 &&
				table.getElementAt(searchX, searchY-1).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			searchTable(table,0,searchY-1,currResult); //continue search from 0,y-1
		} else if ( //if we are searching in the leftmost column, and above is equal to current
				searchY==0 &&
				table.getElementAt(searchX-1, searchY).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			searchTable(table,searchX-1,0,currResult); //continue search from x-1,0
		} else if ( //if the element to the left, above, and above and to the left are all less than current
				table.getElementAt(searchX-1, searchY).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX, searchY-1).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX-1, searchY-1).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			currResult=table.getStringX().charAt(searchX)+currResult; //add found match
			searchTable(table,searchX-1,searchY-1,currResult); //continue search from x-1,y-1
		} else if ( //if the element to the left, above left, and above are equal to current
				table.getElementAt(searchX-1, searchY).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX, searchY-1).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX-1, searchY-1).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			searchTable(table,searchX,searchY-1,currResult); //continue search from x,y-1
			searchTable(table,searchX-1,searchY,currResult); //continue search from x-1,y
			searchTable(table,searchX-1,searchY-1,currResult); //continue search from x-1,y-1
		} else if ( //if the element to the left, and above are equal to current
				table.getElementAt(searchX-1, searchY).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX, searchY-1).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX-1, searchY-1).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			searchTable(table,searchX,searchY-1,currResult); //continue search from x,y-1
			searchTable(table,searchX-1,searchY,currResult); //continue search from x-1,y
		} else if ( //if the element to the left is equal to current
				table.getElementAt(searchX-1, searchY).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX, searchY-1).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX-1, searchY-1).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			searchTable(table,searchX-1,searchY,currResult); //continue search from x-1,y
		} else if ( //if the element above is equal to current
				table.getElementAt(searchX-1, searchY).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX, searchY-1).getSubstructureLength() == 
				table.getElementAt(searchX, searchY).getSubstructureLength() &&
				table.getElementAt(searchX-1, searchY-1).getSubstructureLength() < 
				table.getElementAt(searchX, searchY).getSubstructureLength()) {
			searchTable(table,searchX,searchY-1,currResult); //continue search from x,y-1
		}
	}

	/**
	 * Checks the found substructure against the current result list
	 * 
	 * @param resultToCheck New substructure to check.
	 */
	private void checkResult(String resultToCheck) {
		if (searchResult.isEmpty()) { //if first result
			searchResult.add(resultToCheck);
		} else if (searchResult.indexOf(resultToCheck)!=-1) { //if the new result already in the list
			return;
		} else if (resultToCheck.length()>searchResult.get(0).length()) { //if the new result is longer
			searchResult.clear();
			searchResult.add(resultToCheck);
		} else if (resultToCheck.length()==searchResult.get(0).length()) { //if the new result is the same length
			searchResult.add(resultToCheck);
		}
	}
}
